#ifndef BINARYTREE_H_
#define BINARYTREE_H_

#include "stdio.h"
#include "stdlib.h"

typedef int ElemType;

typedef struct TreeNode {
    ElemType data;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

TreeNode* createTree();

TreeNode* createNode(ElemType data);

TreeNode* createNodeWithChildren(ElemType data, TreeNode* left,
                                 TreeNode* right);

int isEmpty(TreeNode* root);

int isLeaf(TreeNode* root);

int height(TreeNode* root);

ElemType get(TreeNode* root);

void preOrder(TreeNode* root);

void preOrderNor(TreeNode* root);

void preOrderToArray(TreeNode* root, ElemType* arr, int* size);

void inOrder(TreeNode* root);

void inOrderNor(TreeNode* root);

void postOrder(TreeNode* root);

void postOrderNor(TreeNode* root);

void levelOrder(TreeNode* root);

void show(void (*order)(TreeNode*), TreeNode* root);

int count(TreeNode* root);

int countOfKLevel(TreeNode* root, int k);

void freeTree(TreeNode* root);

// 队列，用于层序遍历
typedef struct Node {
    TreeNode* data;
    struct Node* next;
} Node;

typedef struct LinkedQueue {
    Node* front;
    Node* rear;
} LinkedQueue;

typedef LinkedQueue Queue;

LinkedQueue* init_queue();

Node* create_node(TreeNode* data);

int is_empty_queue(LinkedQueue* queue);

int size(LinkedQueue* queue);

void enqueue(LinkedQueue* queue, TreeNode* data);

TreeNode* dequeue(LinkedQueue* queue);

TreeNode* front(LinkedQueue* queue);

// end 队列

// 栈，用于非递归遍历

typedef struct Stack {
    Node* top;
    struct Node* next;
} Stack;

Stack* init_stack();

int is_empty_stack(Stack* stack);

void push(Stack* stack, TreeNode* data);

TreeNode* pop(Stack* stack);

TreeNode* peek(Stack* stack);

// end 栈

#endif  // !BINARYTREE_H_